Discrete Mathematics: Anatomy of a Transport Network

A transport network is a specialized mathematical structure used to model the movement of commodities, data, or materials through a system of restricted conduits. It transforms a standard directed graph into a functional framework by designating specific points of origin and termination, while imposing physical "bottleneck" limits on every connection within the system.

The Definition of a Transport Network

According to Definition 10.1.1, a transport network (or simply a network) is a simple, weighted, directed graph that must satisfy three core criteria:

Property (a): The Source

A designated vertex, the source ($a$ or $s$), represents the point of origin. It has no incoming edges (in-degree = 0) and serves as an infinite supplier.

Property (b): The Sink

A designated vertex, the sink ($z$ or $t$), represents the ultimate consumer. It has no outgoing edges (out-degree = 0).

Property (c): Capacity

The weight $C_{ij}$ of each directed edge $(i, j)$ is called its capacity. This must be a non-negative number ($C_{ij} \geq 0$), representing the maximum possible flow the edge can support.

Real-World Analogy: The Regional Power Grid

To bring these abstract concepts to life, consider a regional electricity network:

The Source: A massive hydroelectric dam. It only produces energy; no electricity enters the dam from the grid itself.
The Sink: A heavy-industrial manufacturing zone. It consumes all incoming electricity to power its machinery; none is returned to the grid.
Edges & Capacities: The transmission lines are the edges. Their capacity is the maximum amperage the physical wires can handle before failing due to heat.
Intermediate Vertices: Local substations that redirect the flow without "consuming" it (Conservation of Flow).

Capacity vs. Flow Nuance

It is critical to distinguish between Capacity and Flow. The capacity $C_{ij}$ is a static physical property—it is the potential volume. The flow $F_{ij}$ is the actual volume being moved at a specific moment. On this slide, we focus exclusively on the architectural limits (capacities) rather than the current state of movement.

🎯 Core Principle: Structural Constraints

Every transport network is a directed graph where flow moves from a supplier (Source) to a consumer (Sink) through conduits limited by non-negative capacities.

Source: $deg^-(a) = 0 \quad | \quad$ Sink: $deg^+(z) = 0 \quad | \quad \text{Capacity}: C_{ij} \geq 0

QUESTION 1

What are the three mandatory components of a transport network according to Definition 10.1.1?

Directed graph, unique source/sink, and non-negative capacities.

Undirected graph, infinite sources, and negative weights.

Weighted graph, bipartite matching, and equal in-degrees.

Simple graph, source with in-degree 1, and zero capacity edges.

QUESTION 2

What is the primary difference between Capacity ($C_{ij}$) and Flow ($F_{ij}$)?

Capacity is the maximum limit; Flow is the actual amount currently moving.

Capacity is dynamic; Flow is a static physical property.

Capacity only applies to the sink; Flow only applies to the source.

There is no difference; they are interchangeable terms in network theory.

QUESTION 3

In the context of a power grid model, what would represent the Source?

A power generation plant like a hydroelectric dam.

A residential neighborhood consuming electricity.

An intermediate substation redirecting power.

The physical copper wires used for transmission.

QUESTION 4

State the condition for a vertex $z$ to be considered a Sink.

It must have an out-degree of zero ($deg^+(z) = 0$).

It must have an in-degree of zero ($deg^-(z) = 0$).

The sum of its capacities must be infinite.

It must be connected to every other node in the graph.

QUESTION 5

[🧩 SYSTEM_FORCED] What is a network? (Focus on Definition 10.1.1 criteria).

A simple, weighted, directed graph with a designated source (no incoming edges), a designated sink (no outgoing edges), and non-negative capacities on all edges.

A bipartite graph where every node has a matching edge.

Any graph that contains a path from node a to node z.

A directed graph where the number of edges equals the number of vertices.